class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        //同余定理: (a-b)/p=k .....0   ->      a%p  ==  b%p
        //c++修正负数%正数为负数： （a%p+P）%p
        unordered_map<int,int> hash;
        hash[0]=1;
        int sum=0,ret=0;
        for(auto e:nums)
        {
            sum+=e;
            int r=(sum%k+k)%k;
            if(hash.count(r))
            ret+=hash[r];
            hash[r]++;
        }
        return ret;
    }
};